package com.mid;

/**
 * Created by Lxk on 2020/1/28.
 */
public class Solution807 {

    public int maxIncreaseKeepingSkyline(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        if (grid[0] == null || grid[0].length == 0) {
            return 0;
        }
        int rowNum = grid.length, colNum = grid[0].length;
        int[] limitRow = new int[rowNum];
        int[] limitCol = new int[colNum];
        for (int i = 0; i < rowNum; i++) {
            int max = 0;
            for (int k = 0; k < colNum; k++) {
                if (grid[i][k] > max) {
                    max = grid[i][k];
                }
            }
            limitRow[i] = max;
        }
        for (int i = 0; i < colNum; i++) {
            int max = 0;
            for (int k = 0; k < rowNum; k++) {
                if (grid[k][i] > max) {
                    max = grid[k][i];
                }
            }
            limitCol[i] = max;
        }
        int increaseNum = 0;
        for (int i = 0; i < rowNum; i++) {
            for (int k = 0; k < colNum; k++) {
                int val = Math.min(limitCol[k], limitRow[i]);
                increaseNum += (val - grid[i][k]);
            }
        }
        return increaseNum;
    }

}
